\documentclass[a4paper,10pt,twocolumn]{article}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc} 
\usepackage{times}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,linkcolor=black,urlcolor=black,citecolor=black]{
hyperref}

%opening
\title{Version distribuée de l'utilitaire GNU/Make}
\author{Arnaud \textsc{Bienner}, Guillaume \textsc{Fauvet}\\
arnaud.bienner@ensimag.imag.fr, guillaume.fauvet@ensimag.imag.fr
}
\date{10 janvier 2010}

\begin{document}

\maketitle
% \clearpage
% \onecolumn
% \tableofcontents
% \twocolumn
% \clearpage

\maketitle

\begin{abstract}
\textit{Le but de ce projet était de fournir une version distribuée du célèbre
utilitaire \textit{GNU/Make}.
}
\end{abstract}

\section{Travail réalisé}
Notre version distribuée de GNU/Make, appelée \underline{Makedist}, a été écrite
en C++ en utilisant la bibliothéque MPI.

Elle permet de distribuer le travail à réaliser par Makedist à travers un réseau
de machines possédant un système de fichiers NFS\footnote{Network File System}
commun.
Notre projet a mis l'accent sur les performances en termes de communications et
localité des données.
De plus, notre version est totalement distribuée: certaines nœuds peuvent jouer
un rôle plus important que les autres mais il n'y a pas de point/serveur
central.
Ce choix a aussi été fait pour des raisons de performances, pour ne pas avoir
une goulot d'étranglement qui risquerait de ralentir tout le système.

\section{Utilisation}
Makedist a été développé en utilisant la dernière version stable de OpenMPI
(1.4), compilé avec les options \verb,--with-threads=posix, et
\verb,--enable-mpi-threads,
afin de permettre l'utilisation des threads.

Il devrait néanmoins pouvoir fonctionner sur d'autres versions de MPI.

Tout comme Make, Makedist utilise le fichiers \verb,Makefile, ou \verb,makefile,
du répertoire courant.

Il est possible d'utiliser l'option \verb,--printgraph,. Le graphe des
dépendances (avec le numéro des machines affectées à chaque nœud) sera alors
affichée, au formet dot\footnote{Il est alors possible de visionner le graphe
directement, avec display, ou d'en faire une image, avec la commande
dot \verb:graph.dot -Tpng > graph.svg: par exemple}. Le programme est alors
arrêté
directement après l'affichage du graphe, et seule le premier nœud affiche le
graphe.

%\section{Architecture du projet et algorithmes utilisés}
\section{Fonctionnement}
\subsection{Initialisation et cœur du programme}
Lors du lancement de Makedist, le programme est exécuté sur chaque machine.
Chacune effectue alors les opérations suivantes :
\begin{enumerate}
 \item Initialisation: récupération de son numéro MPI qui permet de
l'identifier, lancement des threads de communications.
\item Construction du graphe en parsant le Makefile.
\item Coloration du graphe : affectation des tâches au machines de façon
déterministe (afin d'avoir un graphe identique sur chaque machine). Chaque
machine remplit alors une liste de tâches prêtes qu'elle peut exécuter, et une
liste de tâche bloquées qu'elle ne peut pas encore exécutée mais qui lui ont été
affectées.\\
Tant que toutes les tâches ne sont pas finis:
\item Exécution du travail:
\begin{itemize}
 \item Prendre une tâche dans la liste des tâches prêtes
  \item Si la liste est vide, vol de travail
\end{itemize}
\end{enumerate}

\subsection{Lorqu'une tâche est finie}
On parcours la liste des tâches qui dépendent d'elles pour récupérer les
identifiants des machines à prévenir.
On prévient alors les machines.
Peut importe les vols de travail, les tâches bloquées n'étant jamais volé, les
machines à prévenir n'évolueront pas au cours du temps.

\subsection{Vol de travail}
\subsubsection{Vol de travail effectué}
\begin{itemize}
\item VolRéussi = faux;
\item Pour i = 0, i $<$ nombre de machines et que VolRéussi=faux, i++
\begin{itemize}
 \item voler machine d'ont l'identifiant = notre identifiant + 1
 \item si vol réussi, arrêter ; sinon, continuer
\end{itemize}
\item Si toutes les machines ont été volés sans résultats, et si aucune tâche
bloquée n'a été débloquée, attendre un peu puis recommencer.
\end{itemize}
Ainsi, le vol est effectué de proche en proche, afin d'éviter des communications
trop coûteuses.

\subsubsection{Vol de travail subit}

% \section{Détails d'implémentation et expériences}
\section{Expériences}
Les expériences ont été effectuée en utilisant un makefile dont les dépendances
calculent des nombres premiers.
Les ensembles de nombres premiers peut être calculé indépendemment les
uns des autres, mais tous les résultats doivent être fusionnés à la fin.
Notre exemple comportent 20 tâches indépendantes et 1 tâche chargeant de
fusionner les résultats dépendant de toutes les autres.

Nos expériences ont été effectuées sur un nombre variable de machine (entre 1 et
24).
\section{Amélioration possibles}


\end{document}
